Simple LR parser

In computer science, a simple LR or SLR parser will typically have more conflict states than an LALR parser. For real-world computer languages, an SLR parser is usually not adequate, but for student projects in a compiler class it is a good learning tool.

A grammar that has no conflicts reported by an SLR parser generator is an SLR grammar.

Algorithm

The SLR parsing algorithm

Initialize the stack with S
Read input symbol
while (true)
    if Action(top(stack), input) = S
         NS <- Goto(top(stack),input)
         push NS
         Read next symbol
    else if Action(top(stack), input) = Rk
         output k
         pop |RHS| of production k from stack
         NS <- Goto(top(stack), LHS_k)
         push NS
    else if Action(top(stack),input) = A
         output valid, return d
    else
         output invalid, return

Example

A grammar that can be parsed by an SLR parser but not by an LR(0) parser is the following:

(0) S → E
(1) E → 1 E
(2) E → 1

Constructing the action and goto table as is done for LR(0) parsers would give the following item sets and tables:

Item set 0
S → • E
+ E → • 1 E
+ E → • 1
Item set 1
E → 1 • E
E → 1 •
+ E → • 1 E
+ E → • 1
Item set 2
S → E •
Item set 3
E → 1 E •

The action and goto tables:

action goto
state 1 $ E
0 s1 2
1 s1/r2 r2 3
2 acc
3 r1 r1

As can be observed there is a shift-reduce conflict for state 1 and terminal '1'. However, the follow set of E is { $ } so the reduce actions r1 and r2 are only valid in the column for $. The result is the following conflict-less action and goto table:

action goto
state 1 $ E
0 s1 2
1 s1 r2 3
2 acc
3 r1

See also